\chapter[Quantum Information and Computation \\ \textnormal{\emph{Lectured in Lent \oldstylenums{2023} by \textsc{Prof.\ N.\ Datta}}}]{Quantum Information and Computation}
\emph{\Large Lectured in Lent \oldstylenums{2023} by \textsc{Prof.\ N.\ Datta}}

Computers manipulate bits of information to process inputs and answer questions.
Regardless of the physical form of the computer, it has certain fundamental theoretical limitations.
As the size of a bit string increases, the number of possible values of the string increases exponentially, and this means that many computational tasks require exponential amounts of time or space to compute a result.

Quantum computation allows us to bypass some of these limitations by leveraging features of quantum mechanics.
In the quantum case, we store information using quantum bits (`qubits') instead of classical bits.
While a classical computer can only operate on a single state at a time, we can construct a superposition of quantum states and operate on them all at once.
We can use this to solve certain classical problems with a quantum computer faster than is possible with a classical computer, even in theory.

One example of a difficult problem is \( \symsfup{SAT} \), the Boolean satisfiability problem.
The input is a Boolean function in \( n \) variables, and we wish to determine whether there is an assignment of the variables that makes the formula true.
This problem is \( \symsfup{NP} \)-complete: any problem in the complexity class \( \symsfup{NP} \) can be reduced to a case of \( \symsfup{SAT} \).
One of the quantum algorithms discussed in this course is Grover's quantum search algorithm, which solves \( \symsfup{SAT} \) with a quadratic speedup compared to the classical complexity.
This shows that Grover's algorithm can be applied to any \( \symsfup{NP} \) problem to give a quadratic speedup.
Hence, quantum computers can be used to solve a wide class of problems faster than a classical computer can.

\subfile{../../ii/qic/main.tex}
